import time
import random


def generating_data():
    f = open(r'D:/numbers.txt', 'w')
    for i in range(10000):
        f.write(str(random.randint(1,100000))+',')
    f.close()


def insert_sort(num1):
    # 一万条数据时间 16.488942861557007s
    # 时间复杂度O(n)--O(n^2)
    for i in range(1, len(num1)):
        key = num1[i]
        j = i-1
        while j >= 0 and num1[j]> key:
            num1[j+1], num1[j] = num1[j], num1[j+1]
            j -= 1
    return num1


def bubble_sort(num1):
    # 一万条数据时间 16.535946130752563s
    # 时间复杂度O(n^2)
    for i in range(len(num1)):
        for j in range(i+1, len(num1)):
            if num1[i] > num1[j]:
                num1[i], num1[j] = num1[j], num1[i]
    return num1


def selection_sort(num1):
    # 一万条数据时间6.361364126205444s
    # 时间复杂度O(n^2)
    for i in range(len(num1)):
        t = num1[i]
        t1 = i
        for j in range(i+1,len(num1)):
            if t > num1[j]:
                t = num1[j]
                t1 = j
        num1[i],num1[t1] = t, num1[i]
    return num1


def dcc(num1, num2):
    res = []
    i = 0
    j = 0
    while i+j < len(num1)+len(num2):
        # 如果总长度不是列表1和列表2加起来的长度，进入循环
        if i < len(num1) and j < len(num2):
            # 如果列表1和列表2下标没有到其长度，进入判断
            if num1[i] < num2[j]:
                res.append(num1[i])
                i += 1
            else:
                res.append(num2[j])
                j += 1
        else:
            # 如果列表1没有循环完，把列表1剩余数据添加到res后面。
            if i < len(num1):
                res.append(num1[i])
                i += 1
            # 如果列表2没有循环完，把列表2剩余数据添加到res后面。
            else:
                res.append(num2[j])
                j += 1
    return res


def dccsj(num1):
    # 一万条数据时间0.1760098934173584s
    # 如果数组长度大于2，则进入递归。
    if len(num1) >= 2:
        t1 = dccsj(num1[:len(num1)//2])
        t2 = dccsj(num1[len(num1)//2:])
        num1 = dcc(t1, t2)
    return num1

t = [2, 1, 4, 3, 5, 6, 4, 2]
print(dccsj(t))

f = open(r'D:/numbers.txt', 'r')
t = f.read().split(',')
res = []
for i in t:
    if i != '':
        res.append(int(i))


ts = time.time()
# insert_sort(res)
# bubble_sort(res)
# selection_sort(res)
# dccsj(res)
print(time.time()-ts)